import java.util.Arrays;

/**
 * 705. 设计哈希集合
 * https://leetcode-cn.com/problems/design-hashset/
 */
public class Solutions_705 {
    public static void main(String[] args) {
        MyHashSet_705 hashSet = new MyHashSet_705();
        hashSet.add(1);
        hashSet.add(2);
        boolean res1 = hashSet.contains(1);  // output: true
        System.out.println(res1);
        boolean res2 = hashSet.contains(3);  // output: false
        System.out.println(res2);
        hashSet.add(2);
        boolean res3 = hashSet.contains(2);  // output: true
        System.out.println(res3);
        hashSet.remove(2);
        boolean res4 = hashSet.contains(2);  // output: false
        System.out.println(res4);
    }
}

/**
 * 解题一：数组实现 Set（15ms）
 * 添加元素 10，令索引 10 上的 boolean 值为 true
 * 移除元素 10，令索引 10 上的 boolean 值为 false
 * 判断元素 10 是否存在，返回索引 10 上的 boolean 值
 */
class MyHashSet_705 {
    // arrSet[1] = true：元素 1 出现过
    // arrSet[0] = true：元素 0 未出现
    boolean[] arrSet;

    public MyHashSet_705() {
        // 初始 10 个容量
        // 优化：为节省内存，不一次性开辟过多的容量，add 时，发现 key 大于等于数组长度，再扩容
        arrSet = new boolean[10];
    }

    public void add(int key) {
        if (key >= arrSet.length) {
            // 数组需要扩容，否则索引越界
            enlargeSize(key);
        }
        arrSet[key] = true;
    }

    public void remove(int key) {
        if (key >= arrSet.length) {
            // key 不存在
            return;
        }
        // key 存在，boolean 值设置为 false
        arrSet[key] = false;
    }

    public boolean contains(int key) {
        if (key >= arrSet.length) {
            // key 不存在
            return false;
        }
        return arrSet[key];
    }

    /**
     * 数组扩容到 size + 1 个长度
     */
    public void enlargeSize(int size) {
        arrSet = Arrays.copyOf(arrSet, size + 1);
    }
}

